#include<stdio.h>
#include"DoubleLinkList.h"
#include<stdlib.h>
#define true 1
#define false 0

int InitDLinkList(DLlist *list)
{
    list->len=0;
    list->head=NULL;
    list->tail=NULL;
    return true;
}

struct Node *CreateNode(ElementType element)
{
    struct Node *newNode=(struct Node *)malloc(sizeof(struct Node));
    if(newNode==NULL)
    {
        printf("createNode malloc error!\n");
        return NULL;
    }

    newNode->data=element;
    newNode->next=NULL;
    newNode->prev=NULL;
    return newNode;
}

void InsertTail(DLlist *list, ElementType element)
{
    struct Node *newNode=CreateNode(element);
    if(newNode==NULL)
    {
        printf("insert CreateNode error!\n");
        return;       
    }
    if(list->len==0)
    {
        list->head=newNode;
        list->tail=newNode;
    }
    else
    {
        list->tail->next=newNode;
        newNode->prev=list->tail;
        list->tail=newNode;
    }
    list->len++;
}

void InsertHead(DLlist *list, ElementType element)
{
    struct Node *newNode=CreateNode(element);
    if(newNode==NULL)
    {
        printf("insert CreateNode error!\n");
        return;       
    }

    if(list->len==0)
    {
        list->head=newNode;
        list->tail=newNode;
    }
    else
    {
        list->head->prev=newNode;
        newNode->next=list->head;
        list->head=newNode;
    }
    list->len++;        
}

// void InsertIndex(DLlist *list, ElementType element, int index)
// {
//     if(index<0 || index>list->len)
//     {
//         printf("invalid space!\n");
//         return;
//     }

//     struct Node *newNode=CreateNode(element);
//     if(newNode==NULL)
//     {
//         printf("insertindex error!\n");
//         return;
//     }

//     struct Node *TravelPoint=list->head;
//     if(index==0)
//     {
//         newNode->next=TravelPoint;
//         TravelPoint->prev=newNode;
//         newNode->prev=NULL;
//         list->head=newNode;
//         list->len++;
//         return;
//     }

//     if(index==list->len)
//     {      
//         TravelPoint=list->tail;
//         TravelPoint->next=newNode;
//         newNode->prev=TravelPoint;
//         newNode->next=NULL;
              
//         list->tail=newNode;
//         list->len++;
//         return;
//     }

//     while(index!=0)
//     {
//         TravelPoint=TravelPoint->next;
//         index--;
//     }
//     struct Node *PrevNode=TravelPoint->prev;
//     newNode->next=TravelPoint;
//     newNode->prev=PrevNode;

//     PrevNode->next=newNode;
//     TravelPoint->prev = newNode;
//     free(PrevNode);
//     list->len++;
// }

void InsertIndex(DLlist *list,ElementType element,int index)
{
    if(index<0 || index>list->len)
    {
        printf("invalid space!\n");
        return;
    }
    struct Node *newNode=CreateNode(element);
    if(newNode==NULL)
    {
        printf("newNode malloc error!\n");
        return;
    }

    struct Node *TravelPoint=list->head;
    if(index==0)
    {
        newNode->next=TravelPoint;
        newNode->prev=NULL;
        TravelPoint->prev=newNode;
        list->head=newNode;
        list->len++;
        return;
    }
    if(index==list->len)
    {
        TravelPoint=list->tail;
        TravelPoint->next=newNode;
        newNode->prev=TravelPoint;
        newNode->next=NULL;
        list->tail=newNode;
        list->len++;
        return;
    }
    while(index!=0)
    {
        TravelPoint=TravelPoint->next;
        index--;
    }
    struct Node *PrevNode=TravelPoint->prev;
    newNode->next=TravelPoint;
    newNode->prev=PrevNode;

    PrevNode->next=newNode;
    TravelPoint->prev=newNode;
    // free(PrevNode);
    list->len++;
}

void RemoveByIndex(DLlist *list, int index)
{
    if(index<0 || index>=list->len)
    {
        printf("invalid space!\n");
        return;
    }

    if(index==0)
    {
        if(list->len==1)
        {
            free(list->head);
            list->head=NULL;
            list->tail=NULL;
            list->len--;
            return;
        }
        struct Node *temp=list->head;
        list->head=list->head->next;
        list->head->prev=NULL;
        free(temp);
        list->len--;
        return;
    }

    if(index==list->len-1)
    {
        struct Node *temp=list->tail;
        list->tail=list->tail->prev;
        list->tail->next=NULL;
        free(temp);
        list->len--;   
        return;    
    }

    struct Node *TravelPoint=list->head;
    while(index!=0)
    {
        TravelPoint=TravelPoint->next;
        index--;
    }
    // struct Node *PrevNode=TravelPoint->prev;
    // struct Node *NextNode=TravelPoint->next;
    TravelPoint->prev->next=TravelPoint->next;
    TravelPoint->next->prev=TravelPoint->prev;
    free(TravelPoint);
    list->len--;
}

void RemoveByElement(DLlist *list, ElementType element)
{
    int count=FindFirstByElement(list,element);
    while(count!=-1)
    {
        RemoveByIndex(list,count);
        count=FindFirstByElement(list,element);
    }
}

int FindFirstByElement(DLlist *list,ElementType element)
{
    int count=-1;
    struct Node *TravelPoint=list->head;
    while(TravelPoint!=NULL)
    {
        if(TravelPoint->data==element)
        {
            return count+1;
        }
        count++;
        TravelPoint=TravelPoint->next;
    }
    return -1;
}

void SetValueByIndex(DLlist *list,ElementType element,int index)
{
    if(index<0 || index>list->len)
    {
        printf("invalid space!\n");
        return;
    }
    struct Node *TravelPoint=list->head;
    // while((index-1)!=0)
    while(index!=0)
    {
        TravelPoint=TravelPoint->next;
        index--;
    }
    TravelPoint->data=element;
}

void SetValueByElement(DLlist *list,ElementType oldvalue,ElementType newvalue)
{
    struct Node *TravelPoint=list->head;
    if(list->len==0)
    {
        printf("the list is empty,error!\n");
        return;
    }
    if(list->head->data==oldvalue)
    {
        list->head->data=newvalue;
        return;
    }
    while(TravelPoint!=NULL)
    {
        if(TravelPoint->data==oldvalue)
        {
            TravelPoint->data=newvalue;
            TravelPoint->prev->next=TravelPoint;        //不加这段的话从右往左遍历的时候找不到
        }
        TravelPoint=TravelPoint->next;
    }
}

ElementType *FindByIndex(DLlist *list,int index)
{
    if(index<0 || index>list->len)
    {
        printf("invalid space!\n");
        return NULL;
    }
    struct Node *TravelPoint=list->head;
    while(index!=0)
    {
        TravelPoint=TravelPoint->next;
        index--;
    }
    return &TravelPoint->data;
}

int *FindByElement(DLlist *list,ElementType element)
{
    int *findVector=(int *)malloc(sizeof(int)*(list->len+1));
    if(findVector==NULL)
    {
        printf("finfByElement malloc error!\n");
        return NULL;
    }
    struct Node *TravelPoint=list->head;
    int count=0,k=0;
    while(TravelPoint!=NULL)
    {
        if(TravelPoint->data==element)
        {
            findVector[k]=count;
            k++;
        }
        TravelPoint=TravelPoint->next;
        count++;
    }
    findVector[k]=-1;
    return findVector;
}

void Travel(DLlist *list)
{
    printf("next: ");
    struct Node *TravelPoint=list->head;
    while(TravelPoint!=NULL)
    {
        printf("%d ",TravelPoint->data);
        TravelPoint=TravelPoint->next;
    }
    printf("\n");

    printf("prev: ");
    TravelPoint=list->tail;
    while(TravelPoint!=NULL)
    {
        printf("%d ",TravelPoint->data);
        TravelPoint=TravelPoint->prev;
    }
    printf("\n");
}

void FreeDLinklist(DLlist *list)
{
    while(list->head!=NULL)
    {
        struct Node *temp=list->head->next;
        free(list->head);
        list->head=temp;
    }
    list->len=0;
    list->head=NULL;
    list->tail=NULL;
}


